/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._04_03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._04_03
 * @ClassName: ListOfDepth
 * @Author: linyaonan
 * @Date: 2020/3/24 16:58
 */
public class ListOfDepth {

    class MyTreeNode {
        public TreeNode treeNode;
        // 层级
        public int level;

        MyTreeNode(TreeNode treeNode, int level) {
            this.treeNode = treeNode;
            this.level = level;
        }
    }

    public ListNode[] listOfDepth(TreeNode tree) {
        // 异常处理
        if (tree == null) {
            return new ListNode[]{};
        }
        // 用于添加TreeNode
        Queue<MyTreeNode> queue = new LinkedList<>();
        ArrayList<ListNode> result = new ArrayList<>();
        // 头结点
        MyTreeNode headMy = new MyTreeNode(tree, 1);
        queue.add(headMy);

        while (!queue.isEmpty()) {
            // 头结点
            MyTreeNode myTreeNode = queue.remove();
            TreeNode remove = myTreeNode.treeNode;
            // 头结点所处层级
            int level = myTreeNode.level;
            ListNode headListNode = new ListNode(remove.val);
            // 表示链表已经存在
            if (result.size() >= level) {
                ListNode listNode = result.get(result.size() - 1);
                // 找到尾部节点
                while (listNode.next != null) {
                    listNode = listNode.next;
                }
                // 尾部添加
                listNode.next = headListNode;
            } else {
                result.add(headListNode);
            }
            level++;
            TreeNode left = remove.left;
            if (left != null) {
                queue.add(new MyTreeNode(left, level));
            }
            TreeNode right = remove.right;
            if (right != null) {
                queue.add(new MyTreeNode(right, level));
            }

        }

        ListNode[] listNodes = new ListNode[result.size()];
        for (int i = 0; i < result.size(); i++) {
            listNodes[i] = result.get(i);
        }

        return listNodes;
    }

}
